package cn.edu.xjtu.carlWay.tree.commonAncestor;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/**
 * 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * <p>
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/solution/
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        // 该节点及其子树中必然包含至少一个节点
        if (root.val == p.val || root.val == q.val) {
            return root;
        }

        // 判断当前节点的左子树与右子树是否包含至少一个节点
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        if (leftNode != null && rightNode != null) {
            // 如果左子树与右子树都包含一个节点，则说明当前节点就是最近公共子节点
            return root;
        } else {
            // 否则二者必然在不为null的那一边
            return leftNode == null ? rightNode : leftNode;
        }
    }
}
